package com.zwh.algorithm.leetcode.difficulty;

import java.util.*;

public class LeetCode2050 {
    /**
     * 2023-07-28  并行课程 III
     * todo 给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，
     * todo 其中 relations[j] = [prevCoursej, nextCoursej] ，表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）。
     * todo 同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
     * todo 请你根据以下规则算出完成所有课程所需要的 最少 月份数：
     * todo 如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
     * todo 你可以 同时 上 任意门课程 。
     * todo 请你返回完成所有课程所需要的 最少 月份数。
     * todo 注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(minimumTime(3,new int[][]{{1,3},{2,3}},new int[]{3,2,5}));
    }

    /**
     * 记忆化搜索
     * 要求出完成所有课程的最少月份数，可以求出每门课程的最少月份数，然后求出最大值。首先根据
     * relations，构建先修课临接表 prev ,prev[i] 表示课程 i 的所有的先修课。
     * 定义函数 店铺，输入参数为 i ,返回课程 i 所需的最少完成月份。
     * 如果一门课程 i 没有先选修课要求，那么完成它的最少月份数是 time[i]。
     * 如果一门课有先修课时，完成它的最少月份数就是在它的所有先修课的最少完成月份的最大值的基础上，再加上 time[i],即 dp[i]=max(dp[j])+time[i−1],j∈prev[i]。
     * 可以运用记忆化搜索的技巧，求出每门课的最少完成月份数。因为运用了记忆化搜索，每门课的最少完成月份数最多只会被计算一次。
     */
    public static int minimumTime(int n, int[][] relations, int[] time) {
        int mx = 0;
        List<Integer>[] prev = new List[n+1];
        for (int i = 0; i < prev.length; i++) {
            prev[i] = new ArrayList<Integer>();
        }
        for (int[] relation : relations) {
            int x = relation[0], y = relation[1];
            prev[y].add(x);
        }
        Map<Integer,Integer> mone = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            mx = Math.max(mx,dp(i,time,prev,mone));
        }
        return mx;
    }

    private static int dp(int i, int[] time,  List<Integer>[] prev, Map<Integer, Integer> mone) {
        if (!mone.containsKey(i)){
            int mx = 0;
            for (Integer integer : prev[i]) {
                mx = Math.max(mx,dp(integer,time,prev,mone));
            }
            int t = time[i -1];
            mx += t;
            mone.put(i,mx);

        }
        return mone.get(i);
    }

}
